const LinkedNode = require('./linkedNode').LinkedNode;
const SequentialArray = require('./sequentialArray').SequentialArray;

/**
 * 字符串Hash搜索表
 * 
 * @author shuyuan.dai 2021-03-25
 */
class StringHashTable {
    constructor(initCapacity = 1) {
        this.tableSize = this.tableSizeFor(initCapacity);
        this.instance = new SequentialArray(new Array(this.tableSize).fill(null));
    }

    calIndex(code) {
        return ((code & 0xFFFF) ^ (code >>> 16)) & (this.tableSize - 1);
    }

    hashcode(str) {
        let h = 0;
        for (let i = 0; i < str.length; i++) {
            h = 31 * h + str[i].charCodeAt();
        }
        return h;
    }

    add(str) {
        let hashcode = this.hashcode(str), 
            index = this.calIndex(hashcode),
            node = this.instance.elementInIndex(index);
        if(node == null) {
            this.instance.set(index, new LinkedNode(str));
            return;
        }
        let result = node.findUtil2End(str);
        if(result == null) {
            node.add(str);
        }
    }

    has(str) {
        let hashcode = this.hashcode(str);
        let node = this.instance.elementInIndex(this.calIndex(hashcode));
        if(node == null) {
            return false;
        }
        return node.findUtil2End(str) != null;
    }

    tableSizeFor(cap) {
        let n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return Math.max(n + 1, 1);
    }
}

exports.StringHashTable = StringHashTable;